from collections import defaultdict

class Graph:

    def __init__(self):
        self.graph = defaultdict(list)

    def addEdge(self, u, v):
        self.graph[u].append(v)

    def BFS(self, s):
        visited = [False] * (len(self.graph))
        queue = []
        queue.append(s)
        visited[s] = True
        while queue:
            s = queue.pop(0)
            print(s)

            for item in self.graph[s]:
                if visited[item] == False:
                    queue.append(item)
                    visited[item] = True

    def DFS(self, v, visited=None):
        if visited is None:
            visited = [False] * (len(self.graph))
        visited[v] = True
        print(v)
        for item in self.graph[v]:
            if visited[item] == False:
                self.DFS(item, visited)


def test_bft():
    _prepare_graph().BFS(2)

def test_dft():
    _prepare_graph().DFS(2)
    

def _prepare_graph():
    g = Graph()
    g.addEdge(0, 1)
    g.addEdge(0, 2)
    g.addEdge(1, 2)
    g.addEdge(2, 0)
    g.addEdge(2, 3)
    g.addEdge(3, 3)
    return g

                    
if __name__=='__main__':
    test_dft()
